Удвох хлопці почали складати матеріал, роблячи наголос на сильні мелодії, важкі гітарні рифи та й солідні сольні партії інструментів.
Записи потрапили представникам менеджерської фірми "Roasting house productions", і ті одразу ж запропонували Річарду і Петеру контракт. Тепер основним завданням музикантів було зібрати повноцінну команду, і вони приступили до формування складу. Ударник і басист знайшлися майже відразу: ними стали Джоел Ліндер (екс-"Tenebre") і Мартін Везовскі (екс-"The drugs", "Original sin").
З підбором вокаліста довелося добряче попрацювати, але, врешті-решт, цю вакансію зайняв Йонас Блум з "Pole position". Через місяць після укомплектування складу "Majestic" приступили до сесій. Коли альбом був готовий, його розіслали по різних лейблів, і незабаром група отримала декілька контрактних пропозицій. У підсумку за видання "Abstract symphony" взялися "Massacre records" (у Європі), "Toshiba / EMI" (у Японії) і "NEMS" (у Південній Америці). Альбом привернув велику увагу в усьому світі, заробивши хвалебні рецензії в таких виданнях як "Spin city", "Aardshock", "Force", "Powerplay", "Metallium".
Журнал "Metal hammer" виставив "Abstract symphony" сім балів з семи, а "Metal heart" - 9,5 з 10. За виходом платівки було європейське турне "Majestic" в компанії з "Pretty maids". Коли група повернулася з гастролей, музиканти взялися обговорювати новий матеріал.
Проте цього разу до єдиної думки дійти не вдалося, і Еспіноза заявив про свій відхід. Слідом за ним пішли також Ліндер і Блум. Залишилися удвох Річарду і Мартіну знадобився лише місяць, щоб набрати нових рекрутів. Місце біля мікрофона зайняв Аполло Папатанасіу (екс-"Faith taboo"), гітару взяв Магнус Норд, а за ударні сів Петер Вільдоер. Поки вирішувалися кадрові проблеми, у Андерссона була готова левова частка композицій для нового альбому, і "Majestic" залишалося тільки записати ці пісні. Сесії почалися восени 1999-го і на початку наступного року були завершені.
"Trinity overture" був зроблений в кращих традиціях "Rainbow" і Інгві Мальмстіна. Легендарний шведський гітарист після прослуховування цього диску був настільки вражений, що навіть спробував переманити Андерссона у свою команду. Однак клавішник відхилив пропозицію Інгві, оскільки в нього були інші плани. Відкатавши з "Majestic" турне на підтримку "Trinity overture", музикант розпустив свою команду і зібрав новий проект, "Time requiem".