W pierwszej części gry wcieliliśmy się w postać Altaira, członka zakonu asasynów (wyszkolonych zabójców), który przez swoją arogancję i pewność siebie doprowadza do śmierci z rąk templariuszy jednego ze współtowarzyszy. By odbudować swoją reputację w zakonie, podróżuje po Ziemi Świętej i wykonuje misje wyznaczane przez lokalne placówki sekty. Na ulicach największych miast Bliskiego Wschodu tamtych czasów: Jerozolimy, Damaszku i Akki, roi się od wojsk biorących udział w III wyprawie krzyżowej. Jednak to nie największy z problemów, z jakimi przyszło się zmierzyć Altairowi. Na jego drodze stanęli dużo groźniejsi członkowie zakonu templariuszy (Zakon Ubogich Rycerzy Chrystusa i Świątyni Salomona), którzy chcą przejąć władzę nad światem. Pomóc ma im w tym tajemniczy artefakt. Jak się wkrótce okazuje, nie tylko templariusze pałają żądzą jego zdobycia. Także Al Mualim, mistrz skrytobójców, nie może się oprzeć chęci posiadania mocy artefaktu.

Jednak to wszystko wspomnienia. Wspomnienia przodków Desmonda Milesa, który przetrzymywany przez organizację Abstergo (powiązaną z templariuszami) przenosi się w przeszłość za pomocą zaawansowanej technicznie maszyny (zwanej Animusem). Nie odzyska on wolności, póki nie pomoże wskazać miejsca, w którym znajduje się artefakt. Assassin's Creed II rozpoczyna się od ucieczki Desmonda z budynku Abstergo, w czym pomaga mu Lucy (już w pierwszej części było czuć miętę), która jak się okazuje, należy do frakcji współczesnych asasynów. Konflikt pomiędzy asasynami a templariuszami nie skończył się w średniowieczu – on trwa nadal. Tym razem z własnej woli (nie licząc niewielkiego szantażu emocjonalnego ze strony wirtualnej blond piękności) decydujemy się na powrót do wydarzeń z życia jednego ze swoich przodków. Ma to pomóc Desmondowi w zdobyciu wszystkich umiejętności prawdziwego asasyna. Czas i miejsce? Włochy, koniec XV wieku.