If you are talking about the first government issued embossed postal stationery envelope, the penny pink, issued by the UK is almost certainly the first of the type.
Although, preceded by the Mulready, the Mulready was not embossed nor was it an envelope. It was an engraved letter sheet. The penny pink was introduced in February 1841.
Please see the wikipedia article
https://en.wikipedia.org/wiki/Mulready_stationeryBest,
-Larry