diff --git a/services/tunnelbroker/src/cxx_bridge.rs b/services/tunnelbroker/src/cxx_bridge.rs
--- a/services/tunnelbroker/src/cxx_bridge.rs
+++ b/services/tunnelbroker/src/cxx_bridge.rs
@@ -27,6 +27,10 @@
     toSign: String,
     grpcStatus: GrpcResult,
   }
+  struct NewSessionResult {
+    sessionID: String,
+    grpcStatus: GrpcResult,
+  }
 
   unsafe extern "C++" {
     include!("tunnelbroker/src/libcpp/Tunnelbroker.h");
@@ -34,5 +38,14 @@
     pub fn getConfigParameter(parameter: &str) -> Result<String>;
     pub fn isSandbox() -> Result<bool>;
     pub fn sessionSignatureHandler(deviceID: &str) -> SessionSignatureResult;
+    pub fn newSessionHandler(
+      deviceID: &str,
+      publicKey: &str,
+      signature: &str,
+      deviceType: i32,
+      deviceAppVersion: &str,
+      deviceOS: &str,
+      notifyToken: &str,
+    ) -> NewSessionResult;
   }
 }
diff --git a/services/tunnelbroker/src/libcpp/Tunnelbroker.h b/services/tunnelbroker/src/libcpp/Tunnelbroker.h
--- a/services/tunnelbroker/src/libcpp/Tunnelbroker.h
+++ b/services/tunnelbroker/src/libcpp/Tunnelbroker.h
@@ -7,3 +7,11 @@
 rust::String getConfigParameter(rust::Str parameter);
 bool isSandbox();
 SessionSignatureResult sessionSignatureHandler(rust::Str deviceID);
+NewSessionResult newSessionHandler(
+    rust::Str deviceID,
+    rust::Str publicKey,
+    rust::Str signature,
+    int32_t deviceType,
+    rust::Str deviceAppVersion,
+    rust::Str deviceOS,
+    rust::Str notifyToken);
diff --git a/services/tunnelbroker/src/libcpp/Tunnelbroker.cpp b/services/tunnelbroker/src/libcpp/Tunnelbroker.cpp
--- a/services/tunnelbroker/src/libcpp/Tunnelbroker.cpp
+++ b/services/tunnelbroker/src/libcpp/Tunnelbroker.cpp
@@ -2,6 +2,7 @@
 #include "AmqpManager.h"
 #include "AwsTools.h"
 #include "ConfigManager.h"
+#include "CryptoTools.h"
 #include "DatabaseManager.h"
 #include "GlobalTools.h"
 #include "Tools.h"
@@ -9,6 +10,8 @@
 #include "rust/cxx.h"
 #include "tunnelbroker/src/cxx_bridge.rs.h"
 
+#include <glog/logging.h>
+
 void initialize() {
   comm::network::tools::InitLogging("tunnelbroker");
   comm::network::config::ConfigManager::getInstance().load();
@@ -64,5 +67,84 @@
   comm::network::database::DatabaseManager::getInstance().putSessionSignItem(
       *SessionSignItem);
 
-  return SessionSignatureResult{.toSign = toSign};
+  return SessionSignatureResult{
+      .toSign = toSign, .grpcStatus = {.statusCode = GRPCStatusCodes::Ok}};
+}
+
+NewSessionResult newSessionHandler(
+    rust::Str deviceID,
+    rust::Str publicKey,
+    rust::Str signature,
+    int32_t deviceType,
+    rust::Str deviceAppVersion,
+    rust::Str deviceOS,
+    rust::Str notifyToken) {
+  std::shared_ptr<comm::network::database::DeviceSessionItem> deviceSessionItem;
+  std::shared_ptr<comm::network::database::SessionSignItem> sessionSignItem;
+  std::shared_ptr<comm::network::database::PublicKeyItem> publicKeyItem;
+  const std::string stringDeviceID{deviceID};
+  if (!comm::network::tools::validateDeviceID(stringDeviceID)) {
+    return NewSessionResult{
+        .grpcStatus = {
+            .statusCode = GRPCStatusCodes::InvalidArgument,
+            .errorText = "Format validation failed for deviceID"}};
+  }
+  const std::string stringPublicKey{publicKey};
+  const std::string newSessionID = comm::network::tools::generateUUID();
+  try {
+    sessionSignItem = comm::network::database::DatabaseManager::getInstance()
+                          .findSessionSignItem(stringDeviceID);
+    if (sessionSignItem == nullptr) {
+      return NewSessionResult{
+          .grpcStatus = {
+              .statusCode = GRPCStatusCodes::NotFound,
+              .errorText = "Session signature request not found for deviceID"}};
+    }
+    publicKeyItem = comm::network::database::DatabaseManager::getInstance()
+                        .findPublicKeyItem(stringDeviceID);
+    if (publicKeyItem == nullptr) {
+      std::shared_ptr<comm::network::database::PublicKeyItem> newPublicKeyItem =
+          std::make_shared<comm::network::database::PublicKeyItem>(
+              stringDeviceID, stringPublicKey);
+      comm::network::database::DatabaseManager::getInstance().putPublicKeyItem(
+          *newPublicKeyItem);
+    } else if (stringPublicKey != publicKeyItem->getPublicKey()) {
+      return NewSessionResult{
+          .grpcStatus = {
+              .statusCode = GRPCStatusCodes::PermissionDenied,
+              .errorText = "The public key doesn't match for deviceID"}};
+    }
+    const std::string verificationMessage = sessionSignItem->getSign();
+    if (!comm::network::crypto::rsaVerifyString(
+            stringPublicKey, verificationMessage, std::string{signature})) {
+      return NewSessionResult{
+          .grpcStatus = {
+              .statusCode = GRPCStatusCodes::PermissionDenied,
+              .errorText =
+                  "Signature for the verification message is not valid"}};
+    }
+    comm::network::database::DatabaseManager::getInstance()
+        .removeSessionSignItem(stringDeviceID);
+
+    deviceSessionItem =
+        std::make_shared<comm::network::database::DeviceSessionItem>(
+            newSessionID,
+            stringDeviceID,
+            stringPublicKey,
+            std::string{notifyToken},
+            deviceType,
+            std::string{deviceAppVersion},
+            std::string{deviceOS});
+    comm::network::database::DatabaseManager::getInstance().putSessionItem(
+        *deviceSessionItem);
+  } catch (std::runtime_error &e) {
+    LOG(ERROR) << "gRPC: "
+               << "Error while processing 'NewSession' request: " << e.what();
+    return NewSessionResult{
+        .grpcStatus = {
+            .statusCode = GRPCStatusCodes::Internal, .errorText = e.what()}};
+  }
+  return NewSessionResult{
+      .sessionID = newSessionID,
+      .grpcStatus = {.statusCode = GRPCStatusCodes::Ok}};
 }
diff --git a/services/tunnelbroker/src/libcpp/test/DatabaseManagerTest.cpp b/services/tunnelbroker/src/libcpp/test/DatabaseManagerTest.cpp
--- a/services/tunnelbroker/src/libcpp/test/DatabaseManagerTest.cpp
+++ b/services/tunnelbroker/src/libcpp/test/DatabaseManagerTest.cpp
@@ -257,10 +257,6 @@
       database::DeviceSessionItem::DeviceTypes::MOBILE,
       "ios:1.1.1",
       "iOS 99.99.99");
-  EXPECT_EQ(
-      database::DatabaseManager::getInstance().isTableAvailable(
-          item.getTableName()),
-      true);
   database::DatabaseManager::getInstance().putSessionItem(item);
   std::shared_ptr<database::DeviceSessionItem> foundItem =
       database::DatabaseManager::getInstance().findSessionItem(
diff --git a/services/tunnelbroker/src/server/mod.rs b/services/tunnelbroker/src/server/mod.rs
--- a/services/tunnelbroker/src/server/mod.rs
+++ b/services/tunnelbroker/src/server/mod.rs
@@ -1,5 +1,7 @@
 use super::constants;
-use super::cxx_bridge::ffi::{sessionSignatureHandler, GRPCStatusCodes};
+use super::cxx_bridge::ffi::{
+  newSessionHandler, sessionSignatureHandler, GRPCStatusCodes,
+};
 use anyhow::Result;
 use futures::Stream;
 use std::pin::Pin;
@@ -36,9 +38,37 @@
 
   async fn new_session(
     &self,
-    _request: Request<tunnelbroker::NewSessionRequest>,
+    request: Request<tunnelbroker::NewSessionRequest>,
   ) -> Result<Response<tunnelbroker::NewSessionResponse>, Status> {
-    Err(Status::unimplemented("Not implemented yet"))
+    let inner_request = request.into_inner();
+    let notify_token = inner_request.notify_token.unwrap_or(String::new());
+    if !tunnelbroker::new_session_request::DeviceTypes::is_valid(
+      inner_request.device_type,
+    ) {
+      return Err(tools::create_tonic_status(
+        GRPCStatusCodes::InvalidArgument,
+        "Unsupported device type",
+      ));
+    };
+
+    let result = newSessionHandler(
+      &inner_request.device_id,
+      &inner_request.public_key,
+      &inner_request.signature,
+      inner_request.device_type,
+      &inner_request.device_app_version,
+      &inner_request.device_os,
+      &notify_token,
+    );
+    if result.grpcStatus.statusCode != GRPCStatusCodes::Ok {
+      return Err(tools::create_tonic_status(
+        result.grpcStatus.statusCode,
+        &result.grpcStatus.errorText,
+      ));
+    }
+    Ok(Response::new(tunnelbroker::NewSessionResponse {
+      session_id: result.sessionID,
+    }))
   }
 
   type MessagesStreamStream = Pin<