En 1872, con solo 24 años de edad, Palisa marchó a Pula en la península balcánica sobre el mar Adriático en calidad de Director del Observatorio Naval (el puerto de Pola, como entonces se llamaba, fue base de la Armada del Imperio Austro-Húngaro hasta fines de la Primera Guerra Mundial). Allí inició su exitosa labor de descubridor con el asteroide 136 Austria (Marzo 18, 1874). Además, se cuentan de esta época el 153 Hilda (prototipo de un importante grupo de asteroides que orbitan en resonancia 3:2 con Júpiter), el 156 Xanthippe, el 201 Penelope y el célebre asteroide 216 Kleopatra que acaparó titulares de publicaciones científicas en el año 2000, cuando radio observaciones desde Arecibo revelaron su curiosa forma alargada de extremos abultados como un clásico hueso. También desde el Obervatorio Naval, descubrió un cometa (Agosto-21, 1879), el C/1879 Q1 (Palisa). En Pola, contó con un telescopio refractor de 6 pulgadas de diámetro.

El Emperador Francisco José I inauguró el nuevo Observatorio de Viena en 1880. Palisa se ofreció para trabajar como adjunto (similar a un auxiliar nocturno actual) cediendo su posición como director en el Observatorio Naval, para tener oportunidad de usar constantemente el gran refractor de 27" de Viena, para ese entonces el telescopio más poderoso del mundo, con 10.54 metros de distancia focal en un domo de 14 metros de diámetro. Se sabe que Paliza coordinaba un bloque de observaciones a medianoche con sus ayudantes para el gran refractor, pero él continuaba observando sin descanso hasta el alba, usando muchas veces un instrumento menor del observatorio, un refractor de 12" más manejable. Aquí Palisa descubrió 94 nuevos asteroides y varios objetos de cielo profundo que fueron incluidos por J. L. E. Dreyer, siete en su catálogo NGC y dos en el IC