Происходил из дворян Смоленской губернии, родился 4 сентября 1826 г. в Москве. Его отец был внебрачным сыном обер-гофмейстера Петра Романовича Альбедиля. По окончании курса в Пажеском корпусе, 2 августа 1843 г. выпущен корнетом в Лейб-гвардии конный полк, где, продолжая службу, последовательно получил чины поручика (6 декабря 1844 г.), штабс-ротмистра (21 апреля 1848 г.) и ротмистра (30 августа 1848 г.) и принял участие в Венгерском походе 1849 г. 4 ноября 1852 г. назначен командиром эскадрона в своем полку и 25 июня 1853 г. пожалован во флигель-адъютанты. В феврале—мае 1854 г. находился в Витебской губернии для наблюдения за рекрутским набором.
С наступлением Крымской войны, он, произведённый 20 сентября в полковники, был командирован в распоряжение главнокомандующего сухопутными и морскими силами в Крыму князя Меншикова и принял участие в военных действиях; находился в Севастополе во время неприятельских бомбардировок и при отражении атак. Сражение 24 октября 1854 г. под Инкерманом, где он был серьёзно контужен в голову, получив за отличное мужество золотой палаш с надписью «За храбрость» (31 марта 1856 г.), завершило его пребывание в армии, после чего он был отправлен в Оренбург с манифестом о восшествии на престол императора Александра II.
В 1856 г. был командируем в Париж: для передачи чрезвычайных депеш русскому уполномоченному на Парижском мирном конгрессе генерал-адъютанту князю А. Ф. Орлову и затем для поднесения французскому императору Наполеону III орденских знаков св. Андрея Первозванного; в ответ Наполеон наградил Альбединского офицерским крестом ордена Почётного легиона. По выполнении последней миссии Альбединский был награждён орденом св. Станислава 2-й степени (16 апреля 1856 г.) и находился в Москве на коронационных торжествах, по окончании которых снова был отправлен в Париж в качестве корреспондента военного министерства при русском посольстве; за выполнение этой миссии 29 сентября 1857 г. получил орден св. Владимира 4-й степени. Красавец Альбединский, по словам генерала Н. Г. Залесова, близко сошёлся с императрицей Евгенией, вследствие чего Наполеон конфиденциально просил об отозвании его в Россию. Альбединский был отозван и в 1858 г. вернулся в Россию, где 27 сентября получил в командование Лейб-гвардии конно-гренадерский полк; 17 апреля 1860 г., с назначением в Свиту его величества, произведён в чин генерал-майора, 4 мая 1862 г. принял команду над Лейб-гвардии гусарским полком и 4 января 1865 г. назначен начальником штаба войск гвардии и Петербургского военного округа. 27 марта следующего года Альбединский был назначен генерал-адъютантом и 9 октября, с производством в генерал-лейтенанты, назначен Лифляндским, Эстляндским и Курляндским генерал-губернатором и командующим войсками Рижского военного округа; уволенный вслед за тем, 29 сентября 1870 г., по прошению от занимаемых должностей, Альбединский получил орден Белого Орла и четыре года спустя, 22 июля 1874 г. занял пост Виленского, Ковенского и Гродненского генерал-губернатора и командующего войсками Виленского военного округа, и, оставаясь в этих должностях до 1880 г., был произведён 16 апреля 1878 г. в генералы от кавалерии.
Не обладая ни высшим военным образованием, ни особыми военными достоинствами, Альбединский своей военной карьерой был обязан, главным образом, красивой внешности и большим связям при Дворе. Отлично усвоив себе требования военной службы в мирное время, обладая простым здравым смыслом и гуманным сердцем, он проявлял большую заботливость о войсках и пользовался среди них большою популярностью. Служба Альбединского отмечена особенной заботливостью о воспитании и боевой подготовке войск, причём он неоднократно являлся ближайшим руководителем занятий различных комитетов по выработке многих специальных инструкций и положений.
18 мая 1880 г. состоялось назначение Альбединского Варшавским генерал-губернатором и командующим войсками Варшавского военного округа, а 1 января следующего года он назначен членом Государственного совета.
Среди прочих имел ордена св. Станислава 1-й степени (30 августа 1864 г.), св. Анны 1-й степени и императорской короной (7 июля 1867 г.), св. Александра Невского (24 июня 1875 г.), св. Владимира 1-й степени (15 мая 1883 г.).
Умер 19 мая 1883 г. в Варшаве, похоронен на Казанском кладбище в Царском селе.
Альбединский был женат на Александре Сергеевне (урождённой княжне Долгоруковой), у них были дети Мария, Ольга, Александр. Морис Палеолог полагает, что этот брак был устроен Александром II, некоторое время состоявшим с Александрой Сергеевной в связи. Кроме того у Альбединского был внебрачный сын (от графини Ростопчиной) Ипполит (1845 — после 1917, Минский вице-губернатор, гофмейстер).
