Cuando el Hombre halcón vence a unos guerreros mongoles en unas ruinas, encuentra a una chica en una especie de estado catatónico, que balbucea palabras que no puede comprender. Mientras, la Mujer Halcón se encuentra en Irlanda con una chica similar, que también dice cosas que ella no entiende. Cuando ambos regresan con la chica, descubren que se trata de la misma persona y que, combinando las palabras que cada una de ellas dice, se comprende perfectamente el mensaje, que explica que ella es Zatanna, hija del mago Zatara, y que por un hechizo está dividida en dos.

Los halcones juntan las dos figuras y la chica, ya vuelta a la normalidad, les cuenta que su padre ha desaparecido hace mucho tiempo y que ella misma había utilizado su magia para dividirse en dos y buscar en dos posibles sitios al mismo tiempo, pero que había perdido su movilidad y no pudo volver a unificarse. Por eso había hecho aparecer esas reliquias en el museo, ya que conocía sus identidades secretas y sabía que ellos estarían allí y podrían ayudarla. Hawkman se vale de tecnología thanagariana y descubre que Zatara está atrapado en otra dimensión. A pesar de todo, Zatanna decide continuar con su búsqueda.

Con este final abierto, y la seguridad para el lector de que volverá a encontrarse con la hechicera, finaliza la aventura.

Ray Palmer (Atom) recibe una extraña llamada telefónica, en el que una delicada voz femenina le revela que ella sabe que él es Atom. Después del susto, se corporiza una figura que le dice que su nombre es Zatanna, que es una maga y que su padre fue el gran Zatara. Ray Palmer siente alivio, pues Hawkman ya le había hablado de Zatanna y de su búsqueda. Aquí comenzamos a darnos una idea de la magnitud de los poderes de Zatanna, que no sólo puede realizar prodigios mágicos inimaginables, sino que también conoce a su antojo las personalidades secretas de todos los superhéroes.

Zatanna le revela a Atom que en una de sus recientes giras por el mundo a causa de su trabajo como maga, tuvo un contacto psíquico con Zatara, en el que percibió la imagen de un libro mágico que le había pertenecido a su padre. Zatanna trae el libro y le cuenta a Atom que necesita penetrar en el mundo subatómico que hay en su interior para ver si encuentra allí a su padre, y que para eso necesita su ayuda. Atom cree que es imposible, pero ella lo convence de que con la ciencia de él y con su magia podrán lograrlo.

Se reducen y entran en el libro. Allí se enteran de que, efectivamente, Zatara estuvo en este mundo mágico, pero el malvado hechicero que lo gobierna, Druid, lo exilió a un mundo desconocido por todos. Zatanna y Atom logran vencer al hechicero, liberar a la gente que tiene sojuzgada y volver a la Tierra. En el final, ella anticipa que recurrirá a Green Lantern, Flash, e incluso a toda la Liga de la Justicia, si es necesario, para que la ayuden en su búsqueda.

Zatanna y Green Lantern vuelven a la Tierra y se despiden, ya que ella debe continuar con la búsqueda de su padre. En la portada de Green Lantern 42, Zatanna aparece por primera vez integrada a la acción de la misma, junto a Linterna Verde, y nuevamente su participación se destaca con letras de molde. La aventura se titula "El otro lado del mundo".

Zatanna vuelve a aparecer en la segunda aventura de Detective Comics 355, de septiembre de 1966, en compañía de Elongated Man, pero "de incógnito". Como la portada corresponde a la aventura principal del cuaderno, protagonizada por Batman y Robin, nada se anticipa en ella; y en la "splash page" de la historia del Hombre Elástico se nos revela la actuación especial de una "invitada sorpresa" que no aparecerá hasta las últimas páginas y que, efectivamente, es Zatanna.

La aventura se titula "El fantástico caso de los ladrones del trípode" y comienza con dos hombres que están robando joyas y de pronto salen volando, para gran sorpresa de ellos mismos. Elongated Man los ve, intenta detenerlos, e incluso ellos le piden ayuda, pero una fuerza extraña los arrastra hacia quién sabe dónde. Finalmente, llegan a una tienda de artículos teatrales, donde los espera la extraña dama responsable del prodigio. Se vuelve a presentar a Zatanna y a resumir su historia, y ella les explica a los ladrones que había venido a comprar un trípode dorado, pero el dueño le dijo que se lo habían robado. Su magia le permitió localizarlos, y por eso los había traído hasta allí. Los ladrones le dicen que el trípode no tiene valor, ya que no es de oro, y Zatanna les cuenta que para ella es muy importante, porque es mágico, y su magia blanca es nulificada por la magia negra del objeto. Además, les revela que realmente es de oro macizo, pero que su propia magia lo hace parecer falso. El dueño del local la escucha, los amenaza con un arma, y quiere quedarse con el trípode, que vale una fortuna.

Mientras tanto, Elongated Man, que había sido guiado hasta allí por el rastro brillante de unas perlas que se les habían caído a los pillos, llega al lugar y ve a Zatanna, a la que reconoce por la descripción que le habían hecho de ella Hawkman, Atom y Green Lantern. Zatanna está sin poderes, nulificados por la magia negra del trípode, pero con artes marciales y la ayuda del Hombre Elástico logra vencer al dueño de la tienda, que poseía además un libro de I Ching que ella también estaba buscando.

Como se ve, la participación de Elongated Man junto a Zatanna esta vez es accidental. Ella no lo busca, e incluso le pide disculpas por haberlo implicado en el caso. Le cuenta que con el trípode y el libro de I Ching podrá por fin acceder a algunos secretos de magia negra que le permitirán llegar al sitio desconocido donde se encuentra su padre. Elongated Man se ofrece a acompañarla para poder ayudarla, pero ella se niega, ya que en el lugar al que irá no podría sobrevivir ningún hombre común.

La aventura, a pesar de ser muy corta y con una pequeña intervención de la maga, rompe con el esquema tradicional de las anteriores, es mucho más interesante que las otras y se constituye en la antesala directa de la solución del "caso Zatara" iniciado en Hawman 4.

Volviendo a la historia, en ella por fin se produce el postergado encuentro entre padre e hija. La aventura comienza en una sesión de la Liga de la Justicia a la que fueron convocados Atom, Linterna Verde, el Hombre Halcón y Batman, además del Hombre Elástico como invitado, ya que todavía no pertenecía al grupo. Quien los convocó fue Zatanna, que aparece mágicamente frente a ellos y les agradece la ayuda que le prestaron en ocasiones anteriores, ante lo que Batman le responde que él no la había visto antes y que jamás la ayudó. Ella dice que los cinco la ayudaron y relata la historia que ellos no recuerdan, pues estaban bajo los efectos de la magia.

En una tienda de Viena, Zatanna había encontrado la espada de Paracelso, el famoso físico de la Edad Media, en la que vivía encerrado un ser mágico llamado Allura, que le dijo que sabía dónde estaba su padre y que, si la liberaba, le ayudaría a encontrarlo. Para poder liberarla, Zatanna había necesitado el libro de I Ching que le ayudó a encontrar Elongated Man.

Una vez libre, Allura entró en el cuerpo de Zatanna y la condujo a la dimensión de Kharma, donde estaba oculto Zatara. Allí, todos los seres mágicos del lugar la atacaron, comandados por una fuerza extraña, y Zatanna comprendió que sólo convocando a los cinco héroes que ya conocía podría vencer. Así lo hizo, y condujo a los cinco a la dimensión de Kharma, aunque ellos ahora no lo recordaban.

Todos lucharon junto a Zatanna, ignorando que quien dirigía las fuerzas oponentes, unos seres de un antiguo pergamino egipcio, era el mismísimo Zatara, que a toda costa quería evitar que su hija lo hallase.

Batman vuelve a insistir en que ellos no se conocían desde antes, por lo que Zatanna le revela que la anciana bruja con la que habían combatido él y Robin hacía unos meses en Ciudad Gótica era ella misma, que había ido allí intentando encontrar a su padre, hechos que ocurrieron en el Detective Comics 336, de febrero de 1965, en la aventura titulada "La pesadilla embrujada de Batman".

Zatanna vuelve al relato, y les cuenta que Batman, comprendiendo que el enfrentamiento se trataba de un rito para vencer a un ser maligno, ante el asombro de los demás, ordenó que dejaran de luchar y permitieran que los seres del pergamino se llevaran a Zatanna para purificarla de la bruja que la poseía.

Los seres exponen a Zatanna a la luz de una vela mágica, lo que hace que Allura abandone su cuerpo. Inmediatamente, aparece otra Allura, idéntica a la primera pero rubia y vestida de blanco (la otra es morena y viste de negro), se enfrentan y la Allura buena vence. Entonces aparece Zatara, que abraza a su hija después de casi veinte años de no verla, y le cuenta que la Allura malvada fue vencida por él cuando Zatanna era pequeña, y que para que no se escapara la encerró en la espada de Paracelso, por lo que ella lo maldijo diciéndole que si volvía a mirar a su hijita a los ojos, ambos morirían.

Zatara se había exiliado voluntariamente de la Tierra y había vagado todos estos años por varias dimensiones, buscando a la contrapartida buena de Allura para que rompiera el hechizo, y la había encontrado por fin en la dimensión mágica de Kharma.

Súbitamente, Zatara aparece en la reunión cuando su hija termina de relatarles lo ocurrido, y ambos agradecen a los héroes su invalorable ayuda.

En cuanto a la magia del padre y de la hija, desde los inicios de las aventuras de John Zatara en Action Comics (recordemos que aparece por primera vez en Action Comics 1, al igual que Superman), él realizaba sus conjuros deletreándolos al revés, en voz alta, y también su hija utilizó desde su aparición este método, y seguirá haciéndolo, aunque todavía pasará mucho tiempo hasta que se sepan las razones.