What is the first science fiction story that took place outside our own Galaxy? I know that Doc Smith wrote about it in 1934 in Skylark of Valeron, but what about before that? It was not before late 1924 and early 1925 that Hubble published his work which showed the world that our universe was more than just the Milky Way, and so it's not likely that any stories about other galaxies could have been written before that, simply because nobody knew they existed.
In "The Star-Stealers" (Weird Tales, February 1929, available at the Internet Archive) the Patrol fights off extragalactic invaders; however, I believe the action takes place on the fringes of our Milky Way galaxy. Instead I nominate "Outside the Universe", which was first published as a serial in the July, August, September, and October, 1929 issues of Weird Tales, also available at the Internet Archive: Part 1, Part 2, Part 3, Part 4. Quoting Everett F. Bleiler's review in Science-Fiction: The Early Years:
- The third story in the Interstellar Patrol series.
- Dur Nal (an earthman) and his lieutenants Korus Kan (a metal-bodied Antarean) and Jhul Din (a lobster-man from Spica) are on patrol duty at the edge of the galaxy when they see an enormous swarm of spaceships entering from intergalactic space. The newcomers are hostile, flashing a death ray on the patrol squadron and destroying all the vessels except Dur Nal's, which escapes.
- Dur Nal signals to headquarters on Canopus and receives instructions to lure the invaders into a trap in the Crab Cluster. where the galactic battle fleet will be waiting for them.
- Dur Nal leads the invaders on, barely escaping death; on one occasion the patrolmen drive their ship perilously between two adjacent suns. But the battle is a debacle for the Interstellar Patrol. The enemy ships are faster, and their death rays and attractor ships are irresistable.
- Dur Nal and his comrades, however, perform a feat of unparalleled daring: Leaping out into space, they board and capture an invader ship. It was manned by serpent beings, and its records, deciphered at headquarters, reveal what has been happening. The serpent men come from a galaxy so far away that it cannot even be seen on telescopes. Since their galaxy is dying, they are migrating to another more suitable galaxy, and have settled on ours. Along the way they attacked the Andromeda Nebula, but were beaten off.
- The Patrol CO now assigns the three comrades to fly to Andromeda and request help. Otherwise, our galaxy will be lost, since the science and materiel of the Federation of Stars seem inadequate.
- The Patrol vessels move out into intergalactic space, through areas of sudden heat, through radioactive areas, but then the serpent ships appear. A giant attractor seizes Dur Nal's vessel and drags it to a planet in the serpent galaxy. Our comrades are removed from their ship, during which time Jhul Din manages to escape and take off in a spaceship. Dur Nal and Korus Kan, however, are taken to a museum-like establishment, where they are placed in suspended animation like statues, though conscious, until Jhul Din rescues them.
- They are off again for Andromeda, with a fleet of five hundred serpent ships at their heels. They would have lost the race, had not an Andromedan fleet rescued them.
- The Andromedans, the patrolmen are astonished to see, are not organic, but are columns of green living gas. Their science is obviously higher than that of the other two galaxies, and they have regularized their universe with planet-planning. Huge dome-shaped vessels move planets and suns about easily.
- Communication being established by a thought-projector, the Council of Andromeda agrees to aid our galaxy, and a huge fleet sets out into space, including battleships and the planet movers.
- The remainder of the story is a succession of space battles, which must be the longest and most elaborate in the literature to date. The serpent people are decisively defeated, the Andromedan planet-movers providing the finishing touches by exploding suns. Our universe is saved, and the Andromedans return home.
- Miscellaneous points: The architecture of the serpent people is formed of solidified vibrations. The gaseous people of Andromeda live in the hollowed-out interiors of their planets.
A bonus answer. "Outside the Universe" is very probably the correct answer. But it was certainly possible to write stories set in other galaxies before other galaxies were proven to exist, when they were still speculation. Theoretically an earlier extra galactic story could be uncovered.
As I remember, the concept of other galaxies may be mentioned in a science fiction or fantasy novel published in 1908, The House on the Borderland by William Hope Hodgson, though it is a long time since I read it.