Андрій Фединський народився у 1947 році в Інсбруку, Австрія, у таборах для політичних біженців. Коли йому було 8 місяців, родина приїхала до Америки. Його старший брат Джордж народився в Польщі і провів свої підліткові роки у військовій зоні. Молодший брат Петро народився в Пенсильванії після їхньої еміграції до Америки. Коли Андрію було 7 років, сім'я переїхала у Клівленд, штат Огайо, де він навчався в державних школах Клівленду. Згодом він закінчив університет Нотр-Дам зі спеціалізацією англійська та німецька мови. Однією з головних причин, через які Андрій потрапив до Нотр-Дам, було те, що в Інсбруку у 1966-1967 роках він скористався можливістю навчатися ще за однією закордонною програмою навчання.
Після закінчення університету в 1969 році Андрій протягом дев'яти років викладав у державних школах Клівленду. Протягом цього часу він долучився до українського дисидентського руху, Гельсінської спілки та видавництва «Смолоскип», яке публікувало самвидавні матеріали, що були вивезені з Радянського Союзу. Він перекладав українську дисидентську літературу, читав лекції у різних університетах, захищав права людини, і навіть був арештований в Белграді в 1977 році на першій Гельсінській конференції. Щоб привернути увагу до тяжкого становища українських дисидентів, зокрема Миколи Руденка та Олекси Тихого, він та декілька його друзів організували прес-конференцію для країн-учасників, щоб довести їм, що громадяни Радянської України добровільно намагаються допомогти своїй країні реалізувати Гельсінські угоди. Тоді їх заарештували і доставили до суду. Фединського заарештували, посадили на літак і видворили з країни, це було набагато м'якшим покаранням в порівнянні з тими, з якими зіткнулися багато його сучасників. Протягом 1978 року, йому запропонували посаду на Капітолійському пагорбі, щоб працювати письменником і допомагати Бобу Доулю (Bob Dole). Маючи на меті отримати магістерський ступінь з історії в університеті Джона Керролла повертається до Клівленду, згодом він переїхав до Вашингтона, аби працювати разом з конгресменкою Мері Роуз Окар, яка представляла Клівленд. Будучи старшим асистентом, він працював над важливими для міста Клівленду питаннями, такими як розвиток, транспорт, зовнішня політика, а також українська громада. У 1983 році Фединський брав участь у створенні Комісії Конгресу щодо голодоморів.
Поки Фединський працював на Капітолійському пагорбі, його батько Олександр став директором Українського музею-архіву в Клівленді. Саме в цей час Андрій усвідомив масштаб і цінність цієї колекції. Після смерті батька в 1987 році, Андрій повернувся в Клівленд, щоб доповнити колекцію. Те, що мало статися впродовж одного року, розтягнулося на тридцять. Його начальниця Мері Роуз Окар дозволила йому працювати для неї одну половину дня в районному офісі у Клівленді, а інші півдня – в музеї. Протягом цього періоду Фединський упорядкував колекцію, ремонтував будинок, а також здобув грант від житлового розвитку міста (HUD) на будівництво будівлі для архіву. На даний час Тремонт є одним з головних районів Клівленда, де нерухомість коштує мільйони доларів. Наприклад, зал Українсько-Американської Молодіжної Асоціації був куплений за $ 40,000, а тепер його вартість зросла майже до 2-х мільйонів.
На існуючі спроби перенести Український музей-архів до передмістя, Фединський чинив опір. У цьому він заручився допомогою ряду відданих цій справі людей – помічників, колег, друзів. Всі вони вважали, що українська культура повинна залишатись у поєднанні з центральною частиною міста, де розвивається банківська справа, економіка, політика та культура. Якби музей був перенесений на околиці, це було б схоже на його переїзд до села. За словами Фединського, це було б проблемою історичної площини. Адже Україна була сільським суспільством з процвітаючою аграрною культурою, яка дала чудові результати у вигляді прекрасних ремесл, писанкарства і глибоких традицій. Посилаючись на Миколу Хвильового, який бачив у розвитку міста можливість створити міську українську культуру, Фединський вважав, що присутність архіву в міському середовищі Клівленда є важливою підтримкою для УМА, а подальша його інтеграція в околиці що відроджуються, є однією з стратегічних принципів формування майбутніх проектів і планів.