I've done it in France, i wanted to see the impact, and it was a complete waste of money (and it was very expensive, nearly 4000 USD, it was the #1 business magazine in France) : 0 return.
Here are a couple of points that i know work :
-recommendations from other customers
-get your own site to rank well

-buy adwords
-organize some free or cheap training sessions in your area, it usually results in good leads.
-leave business cards here and there (not that many SEO consultants actually have paper business cards, they all depend on their smartphones, big mistake

)
-network with other professionals, they're always in need of help (many of my customers are actually also my competitors!)
hope that helps.
Patrice.