Биография
Родился 7 марта 1875 года в Баку в семье Бакинского губернатора генерал-майора (генерал-лейтенант с 1878 года) Дмитрия Семёновича Старосельского. Из дворян. Православный.
Начало военной карьеры
1 сентября 1893 года поступил в Пажеский Его Императорского Величества корпус. По окончании корпуса 12 августа 1895 года произведён в корнеты и направлен в лейб-гвардии Уланский Её Величества полк.
С 3 марта 1900 по 17 июля 1905 года в запасе. 9 декабря 1904 года произведён в поручики гвардии. 20 апреля 1906 года переименован в штабс-ротмистры армейской кавалерии. 9 декабря 1908 года произведён в ротмистры. На 1 января 1909 года адъютант помощника главнокомандующего Кавказским военным округом. Переименован в ротмистры гвардии в декабре 1912 года. Адъютант генерала от инфантерии, генерал-адъютанта, сенатора, члена Государственного совета, принца Александра Петровича Ольденбургского c 1911 по 1913 год.
Первая мировая война
В конце августа 1914 года добровольцем вступил в Кавказскую туземную конную дивизию. Был назначен помощником командира Татарского конного полка по части строевой. 30 сентября был произведён в подполковники. 24 марта 1916 года назначен командиром Кабардинского конного полка. 10 апреля 1916 года был произведён в полковники.
Из приказа командира Кавказской туземной конной дивизии генерал-лейтенанта Багратиона:
14 мая 1917 года Всеволод Дмитриевич Старосельский был назначен командиром гвардейского Конного полка. Командовал полком до 9 августа 1917 года. С начала 1918 по октябрь 1920 года командовал Персидской его величества шаха казачьей дивизией.
