Yup, that means it's locked to Fido. Koodo will actually do it for you for $35 (if you're not currently a customer with Koodo but trying to get in with your own phone). If you're already with them and you want to just use that phone, than I recommend cellunlocker.net.
You can also see if any of your local mobile shops unlock phones, we have a few here in our local shopping mall that do it. I have had them do my S3, S4,S5 & Note 3 and they always have good prices and have it done in less then 30 minutes. There is also the online cellular unlocking web sites, I have heard some good reviews about http://unlock.canadagsm.ca if you wanted to go that route.