"Anochi Hashem Elokecha asher hotzeisicha mei'eretz Mitzrayim mibeis 'avadim - I am Hashem, your G-d, who has taken you out of the land of Egypt, from the house of slavery." According to most Rishonim, this verse represents the first of the Ten Commandments. Rambam (Seifer HaMitzvos 1) and Ramban (commentary to Chumash) both interpret this verse as a commandment counted in the list of the 613 mitzvos.
Famously, the Ba'al Halachos G'dolos (BeHaG), an enumerator of the 613 mitzvos who preceded the Rambam's Seifer HaMitzvos, surprisingly omits belief in G-d from the list of mitzvos. In defense of BeHag's view, Ramban (hasagos to Seifer HaMitzvos 1) explains that belief in Hashem is a prerequisite to and foundation for other mitzvos since without belief in a M'tzaveh, a commander, one cannot subscribe to any commandment. In defense of this view, Ramban quotes a Mechilta commenting on the inter-relationship between the first two dib'ros. The Mechilta provides a parable about a king who entered a community. When the citizens requested of him to legislate a just legal system for them, he responded, "First accept me as your king; only then can I legislate for you." So too, HKB"H declared to K'lal Yisrael, "I am Hashem Who took you out of Egypt. You all witnessed my Divine miraculous intervention and salvation; do you now accept upon yourself my rulership?" To this the Jewish people replied a resounding "YES!" Then Hashem stated: "Just as you have accepted my rulership, now accept my commandments". He then commanded, "You shall not believe in any other gods (or: gods of others) in My Presence". This Midrash can be interpreted as stated above. Belief is not itself a commandment but is a necessary prelude to all the others. A proof to this view is the fact that this dibbur does not begin with the language of a command such as "ta'amin (believe)" or "teida (know) asher Anochi Hashem Elokecha". Rather, it is stated as a fact: "I am Hashem, your G-d." (Even though Ramban defends BeHag, from his commentary on Chumash it emerges that he himself agrees with Rambam's view.)
This defense of BeHag has been grossly misquoted to imply that some Rishonim treat the foundation of all meaningful existence, belief in the Creator and Law-Giver, as optional, chas v'shalom. Clearly, this is neither the meaning of BeHag nor Ramban's defense of his view. If we are commanded in other mitzvos, then clearly we are also obligated in their fundamental prerequisite, belief in the M'tzaveh. As an example, if one must take a course as part of their college major, they are clearly required to take whatever prerequisites are necessary to enable their taking that course! Ramban is making a technical point: The 613 mitzvos are the list of commandments dictated by the Commander. Belief in that Commander, according to BeHag, cannot be included in the list of commandments, for without such belief one cannot have a commandment. But that very belief clearly is obligatory; otherwise, no commandment could be obligatory, and they certainly are as the fundamental meaning of the word mitzvah implies. In Ramban's own words, "Even though it is a commandment stating 'Know and believe that I am Hashem who took you out of Egypt and perform my commandments', nevertheless, it is not counted in the list since it is the fundamental principle and they are the corollaries as I explained."
This then leaves the approach of Rambam and Ramban himself in need of explanation. Why do they indeed count belief in Hashem as a mitzvah if it should be viewed as a necessary prerequisite and foudnation to other mitzvos. One approach which seems to be implied by Ramban (ibid.) is that fundamental prerequisites are also included in the list of the 613 mitzvos. The Ramban in proving the Rambam's view who counts the mitzvah quoted the same Mechilta about the leader entering town. This implies that his view is that even the initial acceptance of the leader as the legislator should be included in the list of mitzvos.
However, Abarbanel (Rosh Amana) provides an additional insightful answer as to why the Rambam counted belief as a commandment. In the opening paragraph of Mishne Torah, Rambam writes (Y'sodei HaTorah 1:1):
It is the foundation of all foundations and the pillar of all wisdoms to know that there is an Original Existence Who caused all other existences. All existences in heaven and earth and everything in between only were brought into existence from the reality of His Existence.
If one would imagine that He would not exist, nothing else could exist.
[But] if one would imagine that nothing else besides Him would exist, He would still exist and would not cease to exist as a result of their ceasing to exist for all need Him and He does not need any. Therefore His Reality is not like anything else's reality...
This Being is the G-d of the world, the Master of the Earth...He causes all to move without a ... body.
Knowledge of this is a positive commandment as it states, "I am YHVH, your G-d"... One who entertains the belief that there is another god besides This One violates a negative commandment...and denies the fundamental principle which all rests upon.
What emerges from this clearly formulated presentation of Rambam is that just belief in G-d as the Commander is not the nature of the mitzvah of "Anochi Hashem Elokecha". Rather, one is commanded to believe in G-d as the primary and constant Cause of all things Who causes all to occur. Basic belief in G-d as the Commander is indeed a prerequisite and should not be counted in the list even according to Rambam as BeHag apparently maintains. But once one arrives at that belief, it is insufficient. Hashem, the Commander, commands us to know fundamental aspects of His Existence and the distinction between His Existence and all other existences as well.
An additional question is presented by some Rishonim (see Or Hashem by Rav Chasdai Crescas) on the enumeration of belief in Hashem as a commandment. Commandments can address thoughts, statements or actions. But how can commandments be directed at beliefs? A belief is not just a thought or a statement; it is defined as "to hold to be true". But concerning this, "ein m'vo l'bchira bo - there is no access to Free Will concerning this." Either I hold something to be true or I do not; I presumably cannot be commanded to do so! Here also, it is clear that Rav Crescas also viewed belief as obligatory but for a technical reason cannot be counted in the list since it cannot be viewed as a commandment even though it is obligatory. G-d demonstrated His existence through the Exodus and the Revelation of Sinai. The Jewish people experienced all that so they did not need to be commanded.
Here too, Abarbanel, provides a penetrating resolution both elucidating in its explanation of the Rambam's view and guiding as to how we must lead our lives. Some commandments are direct such as dwelling in a sukka or providing for the poor. Some are indirect demanding of us to maintain a certain belief or have a certain feeling. These must be fostered. Abarbanel provides an example concerning love. If one wishes to love someone, he cannot instantaneously do so. He must engage in a relationship, act and think in a certain way to allow that love to occur. Paraphrasing the words of the Abarbanel, "the love itself falls in an instant in an unexplainable way", but this happens because of the activities and thoughts which were done to create it. (This can be compared to Rav Dessler's famous piece "Kuntres HaChessed" that love is created by giving rather than giving being caused by love.) This is also the case concerning the commandment to believe in G-d and aspects of His Divinity. Even if a person does not at first hold them to be true, he is commanded to foster an environment in which this occurs. This comes through study, actions and thinking deeply about the world and life experiences. (Also see Parach Mateh Aharon by Rav Ahron Soloveichik, Hilchos Yesodei HaTorah.) The specific approach to fostering this belief varies, but the common denominator of all of the approaches is that this belief must be worked on. (See for example, Rav Elchanan Wasserman, "Ma'amar 'Al Emuna" in Kovetz Ma'amaarim and Permission to Believe by Rabbi Lawrence Kelemen.) Since there are many levels of belief in G-d, this "fostering" of belief is not a one time activity but a lifetime of effort, of study, of contemplation and of action.
Rambam himself implies this approach in his famous presentation of the mitzvah of loving Hashem (Seifer HaMitzvos 3):
[Hashem] commanded us to love Him, may He be exalted. This [is accomplished] by contemplating and analyzing his commandments and His actions until we comprehend (or reach) Him and take extreme pleasure in this comprehension... The Sifrei states: "Since it states, 'And you shall love Hashem, your G-d', but I do not know how to [do so]? Therefore it states, 'And these words that I command you today shall be on your heart' and with that you will know the One through whose utterances the world came into existence."
The "foundation of all foundations", belief in Hashem, is something that requires constant patient effort and strengthening. Especially in a pleasure-seeking, instant gratification world with prominent atheistic strokes, maintaining and transmitting to our children this most fundamental lifeline to true Reality must be at the top of our priorities.