Ett möte med ryske kollegan Sergej Lavrov är inplanerat under det två dagar långa besöket. Truss har med sig en varning för att en invasion av Ukraina kommer att föra med sig "massiva konsekvenser för alla inblandade" i form av ekonomiska sanktioner från väst.
– Ryssland bör inte känna någon tvekan om kraften i vår respons, sade hon innan hon klev på planet till Moskva.
Truss uppmanar Ryssland att följa internationella överenskommelser som förbinder landet till att respektera Ukrainas självständighet.
Det ryska utrikesdepartementet svarade på onsdagskvällen med ett uttalande där man uppmanar britterna att ändra tonen.
"Relationerna mellan våra länder bör baseras på principen om jämlikhet och ömsesidig respekt, utan konstgjorda restriktioner som förhindrar handel", skriver ryska UD.
I måndags talade Frankrikes president Emmanuel Macron med Rysslands Vladimir Putin under fem timmar, för att sedan fortsätta till Ukraina och dess president Volodomyr Zelenskyj.
Tiotusentals ryska soldater befinner sig vid gränsen mot Ukraina samtidigt som Ryssland förstärker sin militära närvaro i Belarus.