Велиссариу родился в семье зажиточного землевладельца, эмигрировавшего в Румынию из Кими, остров Эвбея. 11 марта 1881 года, закончив греческую гимназию, Велиссариу вступил в греческую армию, в качестве призывника.
В ходе службы и, уже как доброволец, он получил звание капрала.
В 1884 году, получив звание сержанта, поступил в Военное училище унтер-офицеров, которое закончил 7 октября 1887 года, в звании младшего лейтенанта пехоты.
С 25 февраля 1894 года по 24 февраля 1897 года Велиссариу служил в жандармерии.
С началом греко-турецкой войны 1897 года Велиссариу служил командиром взвода 4-й роты /5 пехотного батальона, который находился в подчинении 2-й бригады. Здесь, на перевале Мелуна, Велиссариу впервые проявил свои офицерские качества, удерживая позицию, когда все соседние части отошли.
В последующие годы он был назначен командиром жандармерии на острове Скопелос.
В 1909 году он принял участие в офицерском движении в Гуди.
В 1905 году Велиссариу перевёл и издал книгу французского военного теоретика, в будущем маршала, Фердинанда Фоша «Начала ведения войны» (фр. Les principes de la guerre).