לְמַטֵּה אֶפְרָיִם, הוֹשֵׁעַ בִּן-נוּן.
"Of the tribe of Ephraim, Hoshea the son of Nun."
and then, in pasuk 16:
אֵלֶּה שְׁמוֹת הָאֲנָשִׁים, אֲשֶׁר-שָׁלַח מֹשֶׁה לָתוּר אֶת-הָאָרֶץ; וַיִּקְרָא מֹשֶׁה לְהוֹשֵׁעַ בִּן-נוּן, יְהוֹשֻׁעַ.
"These are the names of the men that Moses sent to spy out the land. And Moses called Hoshea the son of Nun Joshua."
This is something of a big deal. Consider the following pasuk, when Hashem tells His name to Moshe:
וַיְדַבֵּר אֱלֹקִים, אֶל-מֹשֶׁה; וַיֹּאמֶר אֵלָיו, אֲנִי ה.
וָאֵרָא, אֶל-אַבְרָהָם אֶל-יִצְחָק וְאֶל-יַעֲקֹב--בְּאֵל שַׁדָּי; וּשְׁמִי ה, לֹא נוֹדַעְתִּי לָהֶם.
"And God spoke unto Moses, and said unto him: 'I am YKVK;
and I appeared unto Abraham, unto Isaac, and unto Jacob, as God Almighty (Kel Shakkai), but by My name YKVK I made Me not known to them.
Thus, Hashem tells His name YKVK, to Moshe.
There is backup to the assertion that this name was not known before.
A theophoric name is literally one which "carries God." That is, it is a name which contains the name of God in it. We see many such theophoric names in Chumash.
Examples: Shlumiel ben Tzurishaddai, עַמִּיאֵל בֶּן-גְּמַלִּי, סְתוּר בֶּן-מִיכָאֵל, גְּאוּאֵל בֶּן-מָכִי.
However, all those names use the divine names Shakkai and Kel. There is another form of theophoric name, which used Yeho or Yahu in the beginning or end. For example, Yirmiya -> Yirmiyahu. Yechonia -> YehoYachin. Tzidkiyahu. Shallum -> (I would claim) Shelemyahu. And we see Baruch ben Neryah had the theophoric name (they found a signet ring) Berechyahu ben Neryahu.
However, this is in Tanach in general. In Chumash we do not seem to find this. (One exception comes to mind - Yehuda - but that is not what the Yehu in the beginning of his name means.) In Chumash, all we find are the other names of God in theophoric names.
I would claim this shows the truth in Hashem's statement.
וָאֵרָא, אֶל-אַבְרָהָם אֶל-יִצְחָק וְאֶל-יַעֲקֹב--בְּאֵל שַׁדָּי; וּשְׁמִי ה, לֹא נוֹדַעְתִּי לָהֶם
Indeed, we see the Israelites only knew Hashem by the names Kel and Shakkai, and that is what made it into their theophoric names.
Meanwhile, Moshe was introduced to Hashem's name of YKVK, which corresponds to the Yeho/Yahu beginning and ending, and he is the one who gives Hoshea his theophoric name, and uses the Yeho beginning to form Yehoshua.
I just thought this was all really cool...