My own experience was that I had already established a strong background in back-end and data engineering related roles. Although I never had that as my title, that is essentially what I was doing. I had always had an interest in statistics and probability. I was working for a small startup who also had a need for data science skills. In my case I enrolled in a Masters of Data Science program and basically took on the responsibilities of a data scientist over time. Even having done so, it was not necessarily easy to convince recruiters or other employers of my credentials when it was time for me to move on to my next role. I really had to emphasize what I had achieved in particular projects as well as my academic record while working full time. In my current role, the fact that I was writing a Machine Learning book for Manning definitely helped!
While obviously that's not an option for everyone, employers are looking for multiple ways of validating that you are capable of filling the role you are applying for. Other options may be competing in a few kaggle competitions, making some contributions on Github to machine learning related projects, or obtaining related certifications from Amazon, Google or Microsoft.
As someone who is also involved in hiring decisions, I think the certification option is one of the best you can take in terms of investment in time and money.