Односите меѓу Украина и Македонија беа отпочнати на 23 јули 1993 година со признавањето од Украина на државната независност на Бившата Југословенска Република Македонија.

Дипломатските односи биле воспоставени на 20 април 1995 година по пат на размена на ноти меѓу МНР на Украина и МНР на Македонија.

Во јуни 2000 година беше отворено дипломатско претставништво на Украина во Република Македонија.

Во ноември 2001 година беше отворена Амбасада на Украина во Република Македонија.

Амбасадори на Украина во Република Македонија:

06.1999 - 09.2001 - Вјачеслав Похваљскиј

09.2001 - 10.2003 - Павло Кирјаков

03.2004 - 11.2005 - Олексиј Шовкопљас

03.11.2005 - 03.06.2009 - Виталиј Москаленко

03.06.2009 - 21.12.2016 -  Јуриј Гончарук

06.09.2017 -  16.08.2022 - Наталија Задорожњук

26.08.2022 -Лариса Дир