Are they in the same country as you are? Sending a notice and taking legal action would only make sense when they are in the same country as you are.
This what I would have done, If dealing with a vendor outside my country (and having no work contract done except of the email exchange):
1) Send them a reminder about the payment and asking if they faced any issue, because of which the payment has not been made.
2) Send more reminders.
3) After a month or so, email then again that this is a serious issue and with a attached notice to release payment within 7 days.
4) If they never replied to any of my emails, before the end of the 7 days period, I'd tell them that Im going public with this information on complaint websites and forums. Just telling this, might make more than 50% of then send back an email.
Finally, actually posting about them is something Im not sure about, but at least I'd tell them: that Im going to.