Ukraine made their international debut against Georgia in 1991, losing a close game 15-19. The nations played again three days later, and Georgia won again, six to nil. The following year Ukraine met Georgia again for a two match series, again losing both. In their first match of 1993 they defeated Hungary 41-3 for their first win. This was followed by another three wins in succession, against Croatia, Slovenia and Austria. The streak ended in 1994 with a loss to Denmark.
In 1996 Ukraine defeated Latvia 19-3, which would be the start of a nine match winning streak, which would be the longest thus far. The wins carried on into late 1997, until they lost to the Netherlands 13-35. The late 1990s saw mixed results for Ukraine, who defeated teams like Poland and the Czech Republic, but lost games to the likes of Russia, Georgia and Romania.
Ukraine played in the 2005-06 European Nations Cup, which also served as a qualifier for the 2007 Rugby World Cup in France. Ukraine lost all ten of their fixtures and were relegated to the Division 2A. The bottom three teams went onto Round 4 of the European World Cup qualifiers, so Ukraine played Russia twice to determine who goes through. Ukraine lost the games 11-25 and 37-17.