Этимологический словарь Крылова
Образовано от древнерусского окраина — "пограничная местность". Любопытно, что в летописях встречаются такие названия, как Украина Галичьская (область волынского княжества на границе с Польшей) или Украина Псковская (пограничные псковские земли). Первичное значение – юго-западная окраина Московского государства.