1951年4月27日、ニューヨーク州ブルックリンで誕生。父の名は Carl Daniel Frehley、母の名は Esther。エースの本名はポール・ダニエル・フレーリー。父はオランダ移民2世で、母は19世紀から20世紀初頭にドイツから移民してきた Hecht 家の7人兄弟の末っ子だった。父は優れたクラシック・ピアニストで、プロのピアニストを目指すほどだったが、大恐慌で生計を立てる必要があるため、その道を諦めていた。エースは3人兄弟の末っ子として生まれ、1歳年上の兄 Charley と6歳年上の姉 Nancy がいた。幼少期は兄弟の影響でフォーク・ミュージックを聴いて育ち、時折兄のアコースティック・ギターに触れていた。父からピアノの演奏も教わっていたため、ギターの構造を理解するのも早かった。エースの兄姉はともに音楽学校に通うほど、家庭の中には音楽が溢れていた。だが、当時のエースは音楽よりも機械や電子機器に興味を持っていた。これはUFOや宇宙人に関する本や映画の影響だったという。また、エンジニアだった祖父の影響でプレゼントや自分で買った物を分解してしまう性格の始まりでもあった。
13歳の時、友人宅で見た$25のKENTギターと小さなアンプから出る音に衝撃を受ける。エースはそのサウンドに魅了され、自分でこの音をコントロールできたらどんなに楽しいだろうかと想像した。帰宅後すぐに兄からコードを習い始めた。
当時は1964年で The Beatles がアメリカで人気に火がついた時期であった。兄 Charley とエースは当然のように The Beatles にはまり、2人で髪を伸ばし、パートを分け合ってギターを弾いていた。
14歳の誕生日に父親から日本製のエレキ・ギターを贈られ、貯金を崩してアンプを購入。本格的に練習を開始した。15歳になり、兄 Charliy と Micro Organism というバンドを結成するが、ライブをするまでには至らなかった。その後、The Exterminators というバンドで高校のダンス大会で演奏をしている。イギリスの音楽がアメリカで流行し始めると、ピート・タウンゼント、エリック・クラプトン、ジェフ・ベック、ジミー・ペイジ、ジミ・ヘンドリックスといったギタリストから影響を受けるようになった。ビートルズの影響も認めているが、どちらかというとローリング・ストーンズの反骨精神的なイメージに共感を覚えたという。
ギターを弾いていない時のエースは、友人たちとニューヨークを闊歩する、いわゆるストリート・ギャングだった。窃盗、公共物破損、他のグループとの衝突などを繰り返し、セントラル・パークで弓矢を使って狩りをしていたところを警察に補導されたこともあった。
音楽活動と仲間との交友の結果、エースは高校を転々とすることになった。16歳頃から学校でバンドを組み始め、最初のバンド名は Four Roses だった。その後、エースは数々のバンドを渡り歩き、中には数日から長くても数ヶ月という短期間のものもあった。The Exterminator や Honey などのバンドに所属した後、King Kong というバンドでドラマーから「Ace」というニックネームを付けられた。バンドでギターを弾くエースは人気があり、多くの女性を友人に紹介していたという。友人たちは「あいつは、この道に関してエースだな！」と言い始め、それが次第に彼のニックネームとして定着した。
初期のバンドの多くでは、Larry Kelly がリード・シンガーであったが、この Larry Kelly と Sue Kelly の名前はエースの1978年のソロ・アルバムのオープニングを飾る “Rip It Out” の作曲者としてクレジットされており、この曲の一部がそれほど古いものだったのかと驚かされる。
19歳の時、いとこの誕生パーティーで運命的な出会いがあった。Jeanette Trerotolaという1歳年下の女性で、7年後の1976年に二人は結婚した。
数々のバンド活動を通じて、エースはブルックリン一帯で徐々に名が知られるようになった。当時のエースは、長いストレートの髪にベルボトムとしわくちゃなシャツというスタイルで、その姿が目立っていた。この頃、彼の行動が原因で両親から家を追い出され、学校も退学になった。
エースは活動の場をバーに移し、音楽で収入を得始めた。しかし、ある晩、飲み過ぎて酷い演奏をしてしまい、バーのオーナーから支払いを拒否された。激しい口論となり、エースが先に手を出したが、元ボクサーだったオーナーの返り討ちにあった。病院で頬骨を砕かれた状態で目覚め、手術費用は1,500ドルにも及んだ。2ヶ月の入院生活を経て、エースは自身の音楽に対する姿勢を見直す機会を得た。「ここ数年間、ギターの演奏に進歩はあったのか？今後のキャリアを真剣に考えたのか？」この時の内省が、エースをその後の成功へと導くきっかけとなった。
その後数年間、エースは Catheral や Honey and The Magic People といったバンドに所属し、スキー場などのリゾート地でも演奏を行った。
エースの KISS 加入前のバンドで最も有名なのは、Molimo だろう。サウンドとしてはサイケデリックで西海岸ロック風であったが、ギター・ソロはディストーションがかかった歪んだ音で、バンドはエースの演りたいようにさせていたようだ。Molimo は、1971年に Fillmore East や Village Gate という大きめなステージにも上がっている。当時、RCAとアルバム契約まで結んでいたが、録音はされたものの、リリースには至らなかった。
アルバム・リリースの失敗もあり、エースが Molimo を去る時期だと感じていた頃、友人がビレッジ・ボイス誌（1972年12月号）のギタリスト募集広告を教えてくれた。「リード・ギタリスト募集。煌きと才能のある者。アルバム契約あり。時間をムダにしたくない者、連絡乞う。」エースにとって、まさにぴったりの広告だった。
「アルバム契約あり」は決して誇張や嘘ではなかった。実際、その広告を出した当時のポール、ジーン、ピーターには、エピック・レコードと Wicked Lester としての契約があったのだ。
エースはビレッジ・ボイスに連絡し、ポールの連絡先を尋ねた。その後、ポールと電話で話をした。ポールが「1月3日にオーディションを開くから」と言うと、エースは「考えておくよ」とだけ答えた。
