Palisa begann seine astronomische Tätigkeit 1872 als Leiter der österreichischen Marine-Sternwarte Pola im Süden von Istrien, heute Pula, Kroatien. Obwohl ihm dort neben den astrometrischen Instrumenten nur ein 15-cm-Refraktor zur Verfügung stand, konnte er bald einige seiner Asteroiden entdecken. Palisa war der erste Astronom, dem dies für mehr als 50 Kleinplaneten gelang.
Ein größeres Anliegen war ihm jedoch – im Gegensatz zu anderen Forschern – die „Sicherung“ und verlässliche Bahnbestimmung der neu gefundenen Himmelskörper. Denn viele von ihnen gingen noch vor Bekanntwerden der Bahnelemente durch mangelnde Koordination der Beobachtungen verloren.
Im Jahr 1880 wechselte er zur Universitätssternwarte Wien auf eine Assistentenstelle, um am damals weltgrößten 68-cm-Refraktor messen zu können. Von hier aus reformierte er die Bahnberechnung der Asteroiden auf internationaler Basis. Er lokalisierte den Haupt- bzw. Asteroidengürtel (main belt) – in dem die meisten Asteroiden umlaufen – bei 2,2 bis 3,6 Astronomischen Einheiten und fand einige bis zum Mars reichende Bahnen.
Zusammen mit Max Wolf in Heidelberg führte er neue Techniken ein, u. a. den ersten Sternatlas zur Suche und Identifikation, aber auch für Zwecke der Astrophysik. Später entstanden die fotografischen Wolf-Palisa-Sternkarten in 210 Blättern.
Palisa betrieb auch Mond- und Sonnenforschung, z. B. bei der Expedition 1883 zur Sonnenfinsternis in Tahiti, und beteiligte sich an der Suche nach dem hypothetischen sonnennahen Planeten Vulcanus. Er editierte zwei Sternkataloge mit 4700 genauen Örtern – eine wichtige Grundlage zur Bahnsicherung, wofür er 1906 den Preis der Pariser Akademie erhielt.