После завершения Русско-турецкой войны 1828-29 годов Молдавия и Валахия получили автономию. Во время следующей Крымской войны (1853-56 гг.) Молдавия была занята австрийскими войсками, и только после ее окончания, согласно Парижскому договору 1856 года Молдавия и Валахия получили независимость.
Независимые государства могут иметь свои почтовые марки. Поэтому сразу же после подписания Парижского договора было принято решение о почтовой реформе в княжествах. В начале 1858 года были разработаны новые почтовые тарифы на пересылку корреспонденции и было принято решение о выпуске почтовых марок четырех номиналов (27, 54, 81 и 108 пара - в те времена 1 лея=40 пара).
Печать марок производилась вручную, используя одиночное клише на небольшом станке. При печати использовалась бумага разных сортов и разного цвета.
1858. Княжество Молдавия. Первый выпуск. Знаменитые "Бычьи головы" - одни из самых редких марок Европы Исследователи выяснили что существует самая ранняя запись о дате использования марок - это 22 июля 1858 года, что и стали считать днем выхода этих марок. К 150-летнему юбилею "Бычьих голов" в Бухаресте состоялась всемирная филателистическая выставка EFIRO 2008. На ней были показаны те самые клише, с которых и печатались знаменитые марки.
Но эти марки находились в почтовом обращении короткое время. Все же расчет стоимости по утвержденным тарифам был очень сложен (учитывался не только вес, но и расстояние от места назначения). Почтовая администрация решила упростить расчеты, приняв во внимание только вес отправления, как это было принято во многих странах. Новые тарифы вступили в действие с 1 ноября 1858 года. Для реализации новых тарифов были выпущены новые почтовые марки, а оставшиеся на почте марки "Бычьих голов" первого выпуска были уничтожены.