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
@@ -8,10 +8,23 @@
     toSign: String,
     grpcStatus: GrpcResult,
   }
+  struct NewSessionResult {
+    sessionID: String,
+    grpcStatus: GrpcResult,
+  }
 
   unsafe extern "C++" {
     include!("tunnelbroker/src/libcpp/Tunnelbroker.h");
     pub fn initialization();
     pub fn sessionSignatureHandler(deviceID: &str) -> SessionSignatureResult;
+    pub fn newSessionHandler(
+      deviceID: &str,
+      publicKey: &str,
+      signature: &str,
+      deviceType: &str,
+      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
@@ -5,3 +5,11 @@
 
 void initialization();
 SessionSignatureResult sessionSignatureHandler(rust::Str deviceID);
+NewSessionResult newSessionHandler(
+    rust::Str deviceID,
+    rust::Str publicKey,
+    rust::Str signature,
+    rust::Str 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 initialization() {
   comm::network::tools::InitLogging("tunnelbroker");
   comm::network::config::ConfigManager::getInstance().load();
@@ -56,3 +59,78 @@
 
   return SessionSignatureResult{.toSign = toSign};
 }
+
+NewSessionResult newSessionHandler(
+    rust::Str deviceID,
+    rust::Str publicKey,
+    rust::Str signature,
+    rust::Str 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 = 3,
+            .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 = 5,
+              .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 = 7,
+              .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 = 7,
+              .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},
+            std::string{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 = 13, .errorText = e.what()}};
+  }
+  return NewSessionResult{.sessionID = newSessionID};
+}
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
@@ -35,9 +35,39 @@
 
   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 = match inner_request.notify_token {
+      Some(token) => token,
+      _ => String::new(),
+    };
+    let device_type = match inner_request.device_type {
+      1 => String::from("MOBILE"),
+      2 => String::from("WEB"),
+      3 => String::from("KEYSERVER"),
+      _ => {
+        return Err(tools::create_tonic_status(3, "Unsupported device type"));
+      }
+    };
+    let result = cxx_bridge::ffi::newSessionHandler(
+      &inner_request.device_id,
+      &inner_request.public_key,
+      &inner_request.signature,
+      &device_type,
+      &inner_request.device_app_version,
+      &inner_request.device_os,
+      &notify_token,
+    );
+    if result.grpcStatus.statusCode > 0 {
+      return Err(tools::create_tonic_status(
+        result.grpcStatus.statusCode,
+        &result.grpcStatus.errorText,
+      ));
+    }
+    Ok(Response::new(tunnelbroker::NewSessionResponse {
+      session_id: result.sessionID,
+    }))
   }
 
   type MessagesStreamStream = Pin<