Natostyrkans integrationsenhet i Litauen är ett av sex nya centrum som också ligger i Bulgarien, Estland, Lettland, Polen och Rumänien.
Förbindelserna mellan Ryssland och väst har stört Ukrainakonflikten.
Stoltenberg beskrev den nya enheten som ett "stort steg framåt mot större solidaritet... större beredskap".
Han anslöt sig till Litauens president Dalia Grybauskaite vid invigningen i Vilnius på torsdag.
President Grybauskaite välkomnade de nya enheterna i regionen och sade att de skulle säkerställa en snabb och effektiv militärrörelse.
De sex så kallade Natostyrkans integrationsenheter (NFIU) är avsedda att möjliggöra en snabb utplacering av Natos snabbinsatsstyrkor i kristider, rapporterar BBC:s diplomatiska korrespondent Jonathan Marcus.
Vanligtvis kommer de att vara ungefär 45-50 starka bestående av lokal och internationell militär personal, tillägger våra korrespondenter.
De kommer att vidta praktiska åtgärder för utplaceringar, t.ex. identifiering av bränsleförsörjning och lämpliga baser.
Målet är att alla sex enheter ska vara fullt kapabla vid Natos Warszawatoppmöte hösten 2017.
Polen anslöt sig till Nato 1999, sedan 2004 anslöt sig även Bulgarien, Estland, Lettland, Litauen och Rumänien. Alla sex var tidigare i kommunistblocket. De blev EU-medlemmar 2004.
Båda organen anklagar Ryssland för att direkt hjälpa separatister i östra Ukraina med reguljära trupper och tunga vapen. Ryssland förnekar påståendena.
Natos generalsekreterare Jens Stoltenberg har invigt en av alliansens nya befälsenheter som öppnas i Östeuropa under spänningar med Ryssland.